#include "isMatch.h"
bool isMatch(std::string s, std::string p) {
    const int rows = s.size();
    const int cols = p.size();
    std::vector<std::vector<bool>> dp = std::vector<std::vector<bool>>(
        rows + 1, std::vector<bool>(cols + 1, false));
    dp[0][0] = true;
    for (int c = 1; c <= cols; c++) {
        if (p[c - 1] == '*')
            dp[0][c] = dp[0][c - 2];
    }
    for (int row = 1; row <= rows; row++) {
        for (int col = 1; col <= cols; col++) {
            if (s[row - 1] == p[col - 1] || p[col - 1] == '.') {
                dp[row][col] = dp[row - 1][col - 1];
            } else if (p[col - 1] == '*') {
                if (s[row - 1] != p[col - 2] && p[col - 2] != '.')
                    dp[row][col] = dp[row][col - 2];
                else
                    dp[row][col] = dp[row][col - 2] | dp[row - 1][col];
            }
        }
    }
    return dp[rows][cols];
}
